In a communication system, channel encoding is usually adopted to improve reliability of data transmission and ensure quality of communication. A Polar code is a good code which has been proved to be capable of acquiring Shannon capacity and has low encoding/decoding complexity. A Polar code is a linear block code. Its generator matrix is GN., and its encoding process is x1N=u1NGN., where, GN.=BN and a code length is N=2n, n≧0.
Here,
      F    =          [                                    1                                0                                                1                                1                              ]        ,BN is a transposed matrix, such as a bit reversal (bit reversal) matrix.
 is a Kronecker power (Kronecker power) of F, and is defined as =F{circle around (×)}. The Polar code may be expressed as (N, K, A, uAc) by using a coset code. Its encoding process is: x1N=uAGN.(A)⊕uAcGN.(AC), where, A is a set of an information (information) bit index, GN. (A) is a submatrix obtained according to rows that correspond to an index of the set A in GN., and GN.(AC) is a submatrix obtained according to rows that correspond to an index of a set AC in GN.. uAc is a frozen (frozen) bit and is a known bit, where the number of frozen bits is (N−K). For simplicity, these frozen bits may be set to 0.
Decoding of the Polarcodemayuse SC (successive-cancellation, successive-cancellation) decoding, and its process is as follows:
Consider a kind of Polar code, whose parameter is (N, K, A, uAc).
In SC decoding, the following conditional likelihood functions are calculated sequentially:
                                          L            N                          (              i              )                                ⁡                      (                                          y                1                N                            ,                                                u                  ^                                1                                  i                  -                  1                                                      )                          ⁢                  =          Δ                ⁢                                            W              N                              (                i                )                                      ⁡                          (                                                y                  1                  N                                ,                                                                            u                      ^                                        1                                          i                      -                      1                                                        ❘                  0                                            )                                                          W              N                              (                i                )                                      ⁡                          (                                                y                  1                  N                                ,                                                                            u                      ^                                        1                                          i                      -                      1                                                        ❘                  1                                            )                                                          (        1        )            
If i⊂A, decision is made as follows:
                                          u            ^                    i                =                  {                                                                      0                  ,                                                                                                  if                    ⁢                                                                                  ⁢                                                                  L                        N                                                  (                          i                          )                                                                    ⁡                                              (                                                                              y                            1                            N                                                    ,                                                                                    u                              ^                                                        1                                                          i                              -                              1                                                                                                      )                                                                              ≥                  1                                                                                                      1                  ,                                                                              in                  ⁢                                                                          ⁢                  other                  ⁢                                                                          ⁢                  cases                                                                                        (        2        )                                                      If            ⁢                                                  ⁢            i                    ⋐                      A            C                          ,                              simply            ⁢                                                  ⁢            assume            ⁢                                                  ⁢                                          u                ^                            i                                =                      u            i                                              (        3        )            
In the foregoing formulas (2) and (3), ûi represents a decision value of bit ui.
The complexity of the SC decoding is 0 (N log2N). The SC decoding may have good performance and approximate the Shannon limit in the case that the code length N is very long, but when N is relatively short or has an intermediate length, performance of the SC decoding of the Polar code does not exceed performance of a Turbo code and an LDPC (Low-density Parity-check, low-density parity-check) code, and decoding performance needs to be further improved.
Decoding is performed sequentially bit by bit during the SC decoding. After decoding of each bit is completed, a decoded bit is used for subsequent bit decoding after hard decision is performed, and in this way, wrong propagation may exist, thereby causing degradation of the decoding performance. List (list) decoding reserves a plurality of candidate paths and can have decoding performance that approximates the maximum likelihood. SC-List decoding is obtained through the combination of the SC decoding and the List decoding.
A process of the SC-List decoding of the Polar code is briefly described as follows:
Path split: whenever ûi is an information bit (information bit), a current decoding path is split into two paths: one path in the case of ûi=0 and the other path in the case of ûi=1. When the total number of paths exceeds a pre-defined threshold L, a most unreliable path is discarded, only L most reliable paths (called survival path) are maintained; and furthermore, probability values or LLRs (Log-Likelihood Ratio, log-likelihood ratio) on all the paths are updated.
No path split: if ûi is a frozen bit, all decoding paths are not split. It is assumed that ûi=ui, the number of paths is maintained unchanged and probability values (or LLRs) of all the paths are updated.
Existing SC-List decoding adopts the fixed number of survival paths L, and the complexity of the decoding is O (L×N×log2N).
By adopting a scheme of cascading CRC and the Polar code, the Hamming distance (Hamming Distance) can be increased and performance of a code in a high SNR interval can be improved. A simulation result indicates that performance of the cascading scheme is the same as performance of a Turbo code and an LDPC code. However, if a value of the fixed number of existing survival paths is excessively small, a demand for the decoding performance cannot be satisfied; and if a value is excessively large, the decoding complexity is increased.